第二章 线性规划及单纯形法

1.转化为标准形式（min、等号，大于等于 0）

2.查看 m 行 n 列的系数矩阵是否含有 m 阶单位阵，否则大 M or 两阶段

3.求初始基可行解，画出初始单纯形表（取单位矩阵做初始基）
（1）按照规则填入 c_j，C_B，X_B，b，表中间部分系数矩阵 A。（注意同一个基变量的行和列交汇处是 1！！！）
（2）计算检验数σ_j=c_j - Σc_i * a_ij，填入最后一行，计算右下角=基变量的 c_i*b_k 的和的相反数，一般为 0，两阶段法不是 0。

4.对单纯形表中出现的基可行解进行最优性判断
（1）若所有σ_j 都是非负数，则得到最优解，如果存在某个非基变量的σ_j=0，则线性规划有无穷多最优解。
（2）若存在某个σ_k<0，且 a_ik<=0 在 i=1,2,…, m 恒成立，则线性规划具有无界解或无可行解，称无最优解。
（3）若存在某个σ_k<0，且 a_ik(i=1,2,…,m) 不全非负，则进行换基。

5.换基
（1）选进基变量，σ_k=min{σ_j|σ_j<0}，x_k 为进基变量
（2）选出基变量，求最小比值，θ_L=min{b_i/a_ik|a_ik>0}，L 不止一个就任选一个，将第 L 行变量为出基变量，a_Lk 为主元素

6.求新的基可行解，画新单纯形表
（1）X_B、C_B 两列，用换入变量取代换出变量
（2）用初等行变换将主元素 a_Lk 化为 1，同列其他元素化为 0（包括检验数行！！）

大 M 法：引入一个单位矩阵的变量，使其在目标函数系数为 M，每当一个大 M 对应的 X 被移出，就可以不考虑这列。当大 M 无法被换出，则原函数不能最小化
两节短法：引入一个单位阵的变量，第一阶段求解函数使其加和最小，如果最后 w 为 0，进行第二阶段，第二阶段将第一阶段的系数矩阵作为初始单纯形表，将问题转化为原问题继续求解。当第一阶段 w 不等于 0，则原问题无可行解。

布兰德规则：
单纯形法计算中用 规划确定换出变量时,有时存在两个以上相同的最小比值,这样在下一次迭代中就有一个或几个基变量等于零,这就出现了退化解,当出现退化时,进行多次迭代,而基从 ,又返回到 ,即出现计算过程的循环,使永远达不到最优解.为解决这个问题我们介绍勃兰特规则：
（1）当存在两个或两个以上最大检验数时,选取 中下标最小的非基变量 为换入变量；
（2）当按 规则计算时,存在两个或两个以上最小比值时,选取下标最小的基变量为换出变量.